{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Xor Product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #bit-manipulation #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #位运算 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumXorProduct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大异或乘积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你三个整数&nbsp;<code>a</code>&nbsp;，<code>b</code>&nbsp;和&nbsp;<code>n</code>&nbsp;，请你返回&nbsp;<code>(a XOR x) * (b XOR x)</code>&nbsp;的&nbsp;<strong>最大值</strong>&nbsp;且 <code>x</code>&nbsp;需要满足 <code>0 &lt;= x &lt; 2<sup>n</sup></code>。</p>\n",
    "\n",
    "<p>由于答案可能会很大，返回它对&nbsp;<code>10<sup>9 </sup>+ 7</code>&nbsp;<strong>取余</strong>&nbsp;后的结果。</p>\n",
    "\n",
    "<p><strong>注意</strong>，<code>XOR</code>&nbsp;是按位异或操作。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>a = 12, b = 5, n = 4\n",
    "<b>输出：</b>98\n",
    "<b>解释：</b>当 x = 2 时，(a XOR x) = 14 且 (b XOR x) = 7 。所以，(a XOR x) * (b XOR x) = 98 。\n",
    "98 是所有满足 0 &lt;= x &lt; 2<sup>n </sup>中 (a XOR x) * (b XOR x) 的最大值。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>a = 6, b = 7 , n = 5\n",
    "<b>输出：</b>930\n",
    "<b>解释：</b>当 x = 25 时，(a XOR x) = 31 且 (b XOR x) = 30 。所以，(a XOR x) * (b XOR x) = 930 。\n",
    "930 是所有满足 0 &lt;= x &lt; 2<sup>n </sup>中 (a XOR x) * (b XOR x) 的最大值。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>a = 1, b = 6, n = 3\n",
    "<b>输出：</b>12\n",
    "<b>解释： </b>当 x = 5 时，(a XOR x) = 4 且 (b XOR x) = 3 。所以，(a XOR x) * (b XOR x) = 12 。\n",
    "12 是所有满足 0 &lt;= x &lt; 2<sup>n </sup>中 (a XOR x) * (b XOR x) 的最大值。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= a, b &lt; 2<sup>50</sup></code></li>\n",
    "\t<li><code>0 &lt;= n &lt;= 50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-xor-product](https://leetcode.cn/problems/maximum-xor-product/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-xor-product](https://leetcode.cn/problems/maximum-xor-product/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['12\\n5\\n4', '6\\n7\\n5', '1\\n6\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXorProduct(self, a: int, b: int, n: int) -> int:\n",
    "        \n",
    "        if a < b:\n",
    "            a, b = b, a\n",
    "        \n",
    "        mask = (1<<n) - 1\n",
    "        \n",
    "        ax = a & ~mask\n",
    "        bx = b & ~mask\n",
    "        \n",
    "        a &= mask\n",
    "        b &= mask\n",
    "        \n",
    "        left = a ^ b\n",
    "        \n",
    "        ax |= mask ^ left\n",
    "        bx |= mask ^ left\n",
    "        \n",
    "        if left > 0 and ax == bx:\n",
    "            high = 1 << (left.bit_length() - 1)\n",
    "            left ^= high\n",
    "            ax |= high\n",
    "        bx |= left\n",
    "        mo = 10 ** 9 + 7\n",
    "        return ax * bx % mo\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXorProduct(self, a: int, b: int, n: int) -> int:\n",
    "        x = 1 << n\n",
    "        for _ in range(n):\n",
    "            x >>= 1\n",
    "            a_, b_ = a & x, b & x\n",
    "            if   a_ == b_ == 0      : a |=  x; b |=  x\n",
    "            elif a_ != b_ and a >  b: a &= ~x; b |=  x\n",
    "            elif a_ != b_ and a <= b: a |=  x; b &= ~x\n",
    "        #print(a, b)\n",
    "        return (a % 1000000007) * (b % 1000000007) % 1000000007\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        '''\n",
    "        sa, sb, f = bin(a)[2:], bin(b)[2:], True\n",
    "        l = max(len(sa), len(sb))\n",
    "        sa, sb = sa.zfill(l), sb.zfill(l)\n",
    "        #print(sa.zfill(l), sb.zfill(l))\n",
    "        if l > n:\n",
    "            sa_, sb_ = sa[:l - n], sb[:l - n] \n",
    "            sa, sb = sa[l - n:], sb[l - n:]\n",
    "        else:\n",
    "            sa_ = sb_ = '1' * (n - l) \n",
    "        for c1, c2 in zip(sa, sb):\n",
    "            if c1 == c2: \n",
    "                sa_ += '1'\n",
    "                sb_ += '1'\n",
    "            else:\n",
    "                if f:\n",
    "                    sa_ += '1'\n",
    "                    sb_ += '0'\n",
    "                    f = False\n",
    "                else: \n",
    "                    sa_ += '0'\n",
    "                    sb_ += '1'\n",
    "        ###print(sa_, sb_)\n",
    "        return int(sa_, 2) * int(sb_, 2) % 1000000007\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXorProduct(self, a: int, b: int, n: int) -> int:\n",
    "        t1,t2=0,0\n",
    "        for i in range(49,n-1,-1):\n",
    "            t1|=a&(1<<i)\n",
    "            t2|=b&(1<<i)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if (a>>i)&1==(b>>i)&1:\n",
    "                t1|=(1<<i)\n",
    "                t2|=(1<<i)\n",
    "            elif t1<=t2:\n",
    "                t1|=(1<<i)\n",
    "            else:\n",
    "                t2|=(1<<i)                \n",
    "        return (t1*t2)%int(1e9 + 7)\n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumXorProduct(self, a: int, b: int, n: int) -> int:\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            mask = 1 << i\n",
    "            if (a ^ mask) * (b ^ mask) > a * b:\n",
    "                a ^= mask\n",
    "                b ^= mask\n",
    "        return a * b % (10 ** 9 + 7)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
